package Week5.J0517;

public class 最长上升子序列二 {
    public int LIS(int[] a) {
        int n = a.length;
        int[] dp = new int[n + 1];
        int pos = 0;

        for (int x : a) {
            if (pos == 0 || x > dp[pos]) {
                dp[++pos] = x;
            } else {
                int l = 1;
                int r = pos;
                while (l < r) {
                    int mid = (r + l) / 2;
                    if (dp[mid] >= x) r = mid;
                    else l = mid + 1;
                }
                dp[l] = x;
            }
        }
        return pos;
    }
}
